package com.partner.match.utils;

import java.util.List;
import java.util.Objects;

/**
 * @Author: jzz
 * @CreateTime: 2025-02-04
 * @Description: 算法工具类
 */
public class AlgorithmUtils {

    /**
     * 计算标签的距离最短算法
     * @param tags1
     * @param tags2
     * @return
     */
    public static int minTagDistance(List<String> tags1, List<String> tags2) {
        if (tags1 == null || tags2 == null) {
            throw new RuntimeException("参数不能为空");
        }
        int len1 = tags1.size();
        int len2 = tags2.size();

        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化DP数组
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        int cost;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (Objects.equals(tags1.get(i - 1), tags2.get(j - 1))) {
                    cost = 0;
                } else {
                    cost = 1;
                }
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
            }
        }
        return dp[len1][len2];
    }

    /**
     * 距离编辑算法-计算字符串的最小距离值
     * @param word1
     * @param word2
     * @return
     */
    public static int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            throw new RuntimeException("参数不能为空");
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //初始化DP数组
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        int cost;
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    cost = 0;
                } else {
                    cost = 1;
                }
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
            }
        }
        return dp[word1.length()][word2.length()];
    }

    private static int min(int x, int y, int z) {
        return Math.min(x, Math.min(y, z));
    }
}
